package com.lijing.Partition;

import javax.lang.model.util.ElementScanner6;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 给定⼀个字符串 s，将 s 分割成⼀些⼦串，使每个⼦串都是回⽂串。
 * 返回 s 所有可能的分割⽅案。
 * 示例:
 * 输⼊: "aab"
 * 输出: [
 *  ["aa","b"],
 *  ["a","a","b"]
 * ]
 * @title: Patitioning
 * @Author LiJing
 * @Date: 2021/4/59:13 下午
 * @Version 1.0
 */
public class Patitioning {
    static List<LinkedList<String>> result = new ArrayList<>();
    static LinkedList<String> path = new LinkedList<>();

    public static void main(String[] args) {
        String str = "aabaa";
        backTracing(0,str);
        System.out.println(result);
    }

    public static void backTracing(int index, String str){
        /*
         * @Date: 2021/4/5 9:28 下午
         * Step 1: 终止条件
         */
        if (index >= str.length()){
            result.add(new LinkedList<>(path));
            return;
        }

        /*
         * @Date: 2021/4/5 9:29 下午
         * Step 2: 回溯相关操作，单层逻辑
         */
        for (int i = index; i < str.length(); i++) {
            //处理当前节点
            String subString = str.substring(index,i+1);
            if (isPalindrome(subString)){
                path.add(subString);
            }else {
                continue;
            }
            //递归
            backTracing(i+1,str);
            path.removeLast();

        }
    }

    /**
     * 判断字符串是否是回文串
     * @param str str
     * @return 是回文串返回true，否则返回false
     */
    public static boolean isPalindrome(String str){
        if (str.length() == 1){
            return true;
        }
        for (int i = 0; i < str.length()/2; i++) {
            if (str.charAt(i) != str.charAt(str.length()-1-i)){
                return false;
            }
        }
        return true;
    }
}
